﻿class Solution
	2 {
3 public:
	4 int numSquares(int n)
		5 {
		6 vector<int> dp(n + 1);
		7 dp[1] = 1; // 初始化
		8 for (int i = 2; i <= n; i++) // 枚举每个数
			9 {
			10 dp[i] = 1 + dp[i - 1]; // ⾄少等于 1 + dp[i - 1]
			11 for (int j = 2; j * j <= i; j++) // ⽤⼩于 i 的完全平⽅数划分区间
				12 dp[i] = min(dp[i], dp[i - j * j] + 1); // 拿到所有划分区间内的最⼩
			值
				13 }
		14 // 返回结果
			15 return dp[n];
		16 }
	17 };